/**
 * 
 */
package tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import utils.CreateUtils;

/**
 * @author Michael
 *
 * Solution
 * 1, check every node if all nodes in left subtree are smaller than it and all nodes in right subtre are larger than it.
 * O(n^2)
 * 
 * 2, for every node have range to check 0(n) 
 * 
 * 3, pre-order traversal and check if the array is increasing. O(n)
 */
public class ValidateBinarySearchTree {

	// O(n)
	public static boolean validateRecursive(Node<Integer> root, int min, int max) {
		if (null == root)
			return true;

		return (root.value <= max && root.value >= min
				&& validateRecursive(root.left, min, root.value - 1) && validateRecursive(
					root.right, root.value + 1, max));
	}

	// in order, time O(n), space O(1)
	public static boolean validateIterativeIO(Node<Integer> root) {
		if (root == null)
			return true;

		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		Node<Integer> currNode = root;
		int preValue = Integer.MIN_VALUE;
		while (!stack.isEmpty() || currNode != null) {
			if (currNode != null) {
				stack.push(currNode);
				currNode = currNode.left;
			} else {
				Node<Integer> node = stack.pop();
				if (node.value >= preValue) {
					preValue = node.value;
					currNode = node.right;
				} else {
					return false;
				}
			}

		}

		return true;
	}

	// pre order, time O(n), space O(lgn)
	public static boolean validateIterativePO(Node<Integer> root, int minValue,
			int maxValue) {
		if (root == null)
			return true;

		Stack<Node<Integer>> s = new Stack<Node<Integer>>();
		Stack<Integer> maxs = new Stack<Integer>();
		Stack<Integer> mins = new Stack<Integer>();
		s.add(root);
		maxs.add(maxValue);
		mins.add(minValue);
		while (!s.isEmpty()) {
			Node<Integer> node = s.pop();
			int max = maxs.pop();
			int min = mins.pop();
			if (node.value <= max && node.value >= min) {
				if (node.right != null) {
					s.push(node.right);
					mins.push(node.value + 1);
					maxs.push(max);
				}
				if (node.left != null) {
					s.push(node.left);
					mins.push(min);
					maxs.push(node.value - 1);
				}
			} else
				return false;
		}
		return true;
	}

	// level order, time O(n), space O(n)
	public static boolean validateIterativeIO(Node<Integer> root, int minValue,
			int maxValue) {
		if (null == root)
			return true;
		Queue<Node<Integer>> q = new LinkedList<Node<Integer>>();
		Queue<Integer> mins = new LinkedList<Integer>();
		Queue<Integer> maxs = new LinkedList<Integer>();
		q.add(root);
		mins.add(minValue);
		maxs.add(maxValue);
		while (!q.isEmpty()) {
			Node<Integer> node = q.poll();
			int min = mins.poll();
			int max = maxs.poll();
			if (node.value > min && node.value < max) {
				if (node.left != null) {
					q.add(node.left);
					mins.add(min);
					maxs.add(node.value);
				}
				if (node.right != null) {
					q.add(node.right);
					mins.add(node.value);
					maxs.add(max);
				}
			} else
				return false;
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node<Integer> root = CreateUtils.bstWithTenNodes();
		System.out.println(validateIterativeIO(root, Integer.MIN_VALUE,
				Integer.MAX_VALUE));
		root.value = 100;
		System.out.println(validateIterativeIO(root, Integer.MIN_VALUE,
				Integer.MAX_VALUE));
	}

	/**
	 * 
	 */
	public ValidateBinarySearchTree() {
		// TODO Auto-generated constructor stub
	}

}
